home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Monster Media 1996 #15
/
Monster Media Number 15 (Monster Media)(July 1996).ISO
/
math
/
alged34.zip
/
ALGEDSRC.ZIP
/
ALGSORT.C
< prev
next >
Wrap
C/C++ Source or Header
|
1996-06-06
|
4KB
|
135 lines
/*--------------------------------------------------------------------
Alged: Algebra Editor henckel@vnet.ibm.com
Copyright (c) 1994 John Henckel
Permission to use, copy, modify, distribute and sell this software
and its documentation for any purpose is hereby granted without fee,
provided that the above copyright notice appear in all copies.
*/
#include "alged.h"
/*-----------------------------------------------------------------
compare two nodes, if they are equal return 1, else 0.
*/
int equal(node *p,node *q) {
int i;
if (p->kind != q->kind) return 0;
if (p->nump != q->nump) return 0;
if (p->kind==NUM) return p->value==q->value;
if (p->kind==VAR) return !strcmp(p->name,q->name);
if (p->kind==FUN && strcmp(p->name,q->name)) return 0;
for (i=0; i<p->nump; ++i)
if (!equal(p->parm[i],q->parm[i])) return 0;
return 1; /* identical */
}
/*-----------------------------------------------------------------
compare two nodes, return -1 if p<q ,0 if p==q ,1 if p>q.
1. anything < NUM
2. x < y
3. x^3 < x^2 < x < y^3
note: 3 < 2
other operators have same order as left operand.
Historical note... this function WAS used for both sorting and
testing for equality. However, for maintenance and efficiency
reasons I found it better to make a separate "equal" function.
*/
int cmp(node *p,node *q) {
int r,i,j,k;
if (p->kind==NUM) /* NUMERIC */
if (q->kind==NUM)
return p->value==q->value ? 0 :
p->value < q->value ? 1 : -1; /* hi to low */
else return 1;
else if (q->kind==NUM)
return -1;
j = (p->kind==MUL && p->rt->kind==NUM);
k = (q->kind==MUL && q->rt->kind==NUM);
if (j && !k) {
r = cmp(p->lf,q); /* IGNORE COEFFICIENTS */
if (r) return r;
return 1;
}
if (k && !j) {
r = cmp(p,q->lf);
if (r) return r;
return -1;
}
if (p->kind==VAR) { /* VARIABLES */
if (q->kind==VAR)
return strcmp(p->name,q->name);
else if (q->nump) {
r = cmp(p,q->lf);
if (r) return r;
}
return 1;
}
else if (q->kind==VAR) {
if (p->nump) {
r = cmp(p->lf,q);
if (r) return r;
}
return -1;
}
if (p->kind==FUN && q->kind==FUN) { /* FUNCTIONS */
r = strcmp(p->name,q->name);
if (r) return r;
}
k = q->kind-p->kind;
if (!k) k=p->nump-q->nump;
if (!k) { /* ARE THEY IDENTICAL? */
for (i=0; i<p->nump; ++i) {
r = cmp(p->parm[i],q->parm[i]);
if (r) return r;
}
return 0; /* identical */
}
if (p->nump && q->nump) { /* DIFFERENT OPERATORS */
if (k>0) r = cmp(p->lf,q);
else r = cmp(p,q->lf);
if (r) return r;
}
return k;
}
/*-----------------------------------------------------------------
sort over operator. oper = ADD or MUL.
This uses bubble sort. It assumes that the nodes have been
adjusted to left association. For best results, call bisect
before calling this.
*/
int sortnode(node *p,int oper) {
int i,r=0;
node *s,**t;
if (p->kind!=oper) {
for (i=0; i<p->nump; ++i)
r+=sortnode(p->parm[i],oper);
return r;
}
while (p->kind==oper) {
s=p;
t=p->parm+1;
while (s->lf->kind==oper) {
s = s->lf;
if (cmp(s->rt,*t)>0) t=s->parm+1;
}
if (cmp(s->lf,*t)>0) t=s->parm;
if (*t != p->rt) { /* too much indirection? */
s = *t;
*t = p->rt;
p->rt = s;
++r;
}
r+=sortnode(p->rt,oper);
p = p->lf;
}
r+=sortnode(p,oper);
return r;
}